#include<stdio.h>


/*
	不带头节点的链表从小到大排序
	直接插入排序的思想
*/
LinkList LinkListSort(LinkList *L)
{//L是不带头节点的线性链表,链表结点构造为data和link两个域
 //data是数据域,link是指针域
 //本算法将该链表按结点数据域的值的大小,从小到大重新链接

	p = L -> link;//p是工作指针,指向待排当前元素
	L -> link = NULL;//断链,假定第一个元素有序,即只有一个结点

	while(p != NULL)
	{
		r = p -> link//r是p的后继
		q = L;

		if(q -> data > p -> data)
		{//待排序元素比第一个元素小
			p -> link = L;
			L = p;
		}
		else
		{
			while(q -> link != NULL && q -> link -> data < p -> data)
				q = q -> link;

			p -> link = q;
			q -> link = p;
		}

		p = r;//指向下个待排结点
	}

}

/*
	已知递增有序的单链表A,B和C分别存储了一个集合，
	设计算法实现A：=A∪（B∩C），
	并使求解结构A仍保持递增。
	要求算法的时间复杂度为O(|A|+|B|+|C|)。
	其中,|A|为集合A的元素个数

	[算法讨论]本算法先找结果链表的第一个元素，这是因为题目要求结果表要递增有序（即删除重复元素）。
	这就要求当前待合并到结果表的元素要与其前驱比较。
	由于初始pre=A（头结点的头指针），这时的data域无意义，不能与后继比较元素大小，因此就需要确定第一个元素。
	当然，不要这样作，而直接进入下面循环也可以，但在链入结点时，必须先判断pre是否等于A，这占用了过多的时间。
	因此先将第一结点链入是可取的。
    算法中的第二个问题是要求时间复杂度为O（|A|+|B|+|C|）。
    这就要求各个表的工作指针只能后移（即不能每次都从头指针开始查找）。本算法满足这一要求。
    最后一个问题是，当B，C有一表为空（即B和C已无公共元素时），要将A的剩余部分链入结果表。

*/
LinkList unions(LinkList *A, LinkList *B, LinkList *C)
{//A,B和C均是带头结点的递增有序的单链表，本算法实现A= A∪（B∩C），使求解结构保持递增有序。

	pa=A->next;pb=B->next;pc=C->next;//设置三个工作指针。
 	pre=A;//pre指向结果链表中当前待合并结点的前驱。

 	if(pa->data<pb->data||pa->data<pc->data)//A中第一个元素为结果表的第一元素。
    {
    	pre->next=pa;pre=pa;pa=pa->next;
    }
	else{
		while(pb&&pc)
		{//找B表和C表中第一个公共元素。
      		if(pb->data<pc->data)
      			pb=pb->next;
      		else if(pb->data>pc->data)
      			pc=pc->next;
            else 
            	break;//找到B表和C表的共同元素就退出while循环。
        }

    	if(pb&&pc)
    	{//因共同元素而非B表或C表空而退出上面while循环。
        	if(pa->data>pb->data)//A表当前元素值大于B表和C表的公共元素，先将B表元素链入。
        	{
        		pre->next=pb;pre=pb;pb=pb->next;pc=pc->next;
        	}//B，C公共元素为结果表第一元素。
        }
        else
        {//B,C无公共元素
        	pre->next=pa;pre=pa;pa=pa->next;
        }
      }//结束了结果表中第一元素的确定

	while(pa&&pb&&pc)
  	{
  		while(pb&&pc)
	 	{
     		if(pb->data<pc->data) 
     			pb=pb->next;
     		else if(pb->data>pc->data) 
     			pc=pc->next;
          	else 
          		break;//B表和C表有公共元素。
    	}

   		if(pb&&pc)
    	{
    		while(pa&&pa->data<pb->data)//先将A中小于B，C公共元素部分链入。
        	{
        		pre->next=pa;pre=pa;pa=pa->next;
        	}

   			if(pre->data!=pb->data)
		  	{
		  		pre->next=pb;pre=pb;pb=pb->next;pc=pc->next;
		  	}
   			else
   			{
   				pb=pb->next;pc=pc->next;
   			}//若A中已有B，C公共元素，则不再存入结果表。
      }

   }//while(pa&&pb&&pc)
  if(pa) 
  	pre->next=pa;//当B，C无公共元素（即一个表已空），将A中剩余链入。
}//算法Union结束


/*
	输入一个正整数数组，把数组里所有数字拼接起来排成一个数，
	打印能拼接出的所有数字中最小的一个。
	例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

	思路 冒泡排序, 但是排序的条件为 mn > nm n就在前面
*/
int compare(int a,int b)
{ //如果 ab > ba返回1 否则返回0
	char index[]="0123456789";
	char *c1,*c2;//c1存ab， c2存ba
	int i = 0, n = 0;//n记录字符串的长度
	do
	{
		if(a != 0) 
			{c1[i++] = index[a%10]; a = a%10;n++;}
		else
			{c1[i++] = index[b%10];b = b%10;n++;}	

	}while(a != 0 || b != 0);

	i = 0;

	do
	{
		if(b != 0)
			{c2[i++] = index[b%10];b = b%10;n++;}
		else
			{c2[i++] = index[a%10];a = a%10;n++;}
	}while(a != 0 || b != 0);
	
	for(i = 0; i <n; i++)
	{
		if(c1[i]<=c2[i])
			return -1; 
	}

	return 1;
}

void Bubble(int *A, int n)
{
	for(int i = 0; i < n; i++)
	{
		int tag = 0;

		for(int j = 0; j < n-i; j++)
		{
			if()
		}
	}
}

/*
	输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
	假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，
	序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列	。
	（注意：这两个序列的长度是相等的）

	思路：

　　建立一个辅助栈s,把序列1,2,3,4,5依次压入辅助栈s，并按照第二个序列4,5,3,2,1的顺序从辅助栈s中弹出数字。
*/
int IsPopOrder(int pushV[],int popV[],int n)
{
	if(n==0) return 0;
	int stack[10],i,j,top=-1;
	for(i=0,j=0;i<n;)
	{
		stack[++top]=pushV[i++];
		while(j<n&&stack[top]==popV[j]){top--;j++;}
	}
	return top==-1?1:0;;
}

/*
	判断单链表是否成环
	寻找环的入口
*/

/*
	顺序表逆序数个数
*/
int mergesort(int *A, int n)
{
	if(n <= 0)
		return -1;
	int tmp[n];
	int count = mergemid(A, 0, n-1, tmp);;
	
	free(tmp);

	return count;
}

int mergemid(int *A, int p, int r, int tmp)
{
	int count1, count2, count3;
	if(p < r)
	{
		mid = (p+r)/2;
		count1 = mergemid(A, p, mid, tmp);
		count2 = mergemid(A, mid+1, r,tmp);
		count3 = merge(A, p, mid, r, tmp);
		return count1 + count2 + count3;

	}
}

int merge(int *A,int p, int mid, int r, int *tmp)
{
	int i = p;    int j = mid + 1;
	int n = mid;  int m = r;
	int k = 0;    int count;
	while(i <= n && j <= m)
	{
		if(A[i] <= A[j])
			tmp[k++] = A[i++];
		else
		{
			tmp[k++] = A[j++];
			count = n - i + 1;
			//左边的大于右边的，则左边后面的个数是该规模下所有逆序对的个数
		}	

	}

	while(i<=n)
		tmp[k++] = A[i++];
	while(j<=m)
		tmp[k++] = A[j++];
	return count;
}

/*
	设整数x1,x2,…,xN已存放在数组A中，编写一c语言递归函数，
	输出从这n个数中取出所有k 个数的所有组合（k<=n）。
	例：若A中存放的数是1，2，3，4，5，k为3，
	则输出结果应为：543，542，541，532，531，521，432，431，421，321。
*/
int B[10];
int A[]={1,2,3,4,5};
void combination(int i,int j,int k)
 {
	 int t;
	if(k==0){for(t=0;t<j;t++) printf("%d ",B[t]);printf("\n");return;}
	if(i-k+1>=0)
	{
		B[j++]=A[i];
		combination(i-1,j,k-1);//包含A[i],从剩下的找k-1个数
		combination(i-1,j-1,k);//不包含A[i]，从剩下找k个数
	}
 }


/*
	给定一棵二叉搜索树，请找出其中的第k小的结点。

	思路: 中序遍历找到第k个

*/

 /*
	给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
	注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
	二叉树采用的三叉链表存储的，包含其父节点


 */

typedef struct Bitree
{
	int data;
	struct Bitree *Lchild, *Rchild, *father;
};

Bitree inordernext(Bitree *T, Bitree *p)
{
	if(p==NULL)
        return NULL;
    if(pNode->right!=NULL)
    {
        pNode=pNode->right;
        while(pNode->left!=NULL)
            pNode=pNode->left;
        return pNode;
    } 
    
    while(pNode->next!=NULL)
    {
        TreeLinkNode *proot=pNode->next;
        if(proot->left==pNode)
           	return proot;
        pNode=pNode->next;
    }
    
    return NULL;
}

/*
	冒泡排序算法是把大的元素向上移（气泡的上浮），
	也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。
*/
void sort(int A[],int n)
{
	int i=0,j=n, k,flag=0;
	while(i<j)
	{
		flag=0;
		for(k=i;k<j;k++) //上浮
		{
			if(A[k]>A[k+1]) {swap(A[k],A[k+1]);flag=1;}
		}
		j--;
		for(k=j;k>i;k--)//下沉
		{
			if(A[k]<A[k-1]) {swap(A[k],A[k-1]);flag=1;}
		}
		i++;
		if(flag==0) break;
	}
}

/*
	给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。
	例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，
	那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}；
	针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： 
	{[2,3,4],2,6,2,5,1}， 
	{2,[3,4,2],6,2,5,1}， 
	{2,3,[4,2,6],2,5,1}，
	{2,3,4,[2,6,2],5,1}， 
	{2,3,4,2,[6,2,5],1}， 
	{2,3,4,2,6,[2,5,1]}。
*/

/*
	设计算法，以不多于 1.5n 的比较次数，找长度为n的顺序表的最大值和最小值
	一对数,先进行比较,较大数与max比较,较小的数与min比较
	初值分两种情况 
	当n为奇数时,max和min的初值为第一个数
	当n为偶数时,前两个数中较大的值赋值给max,较小的数赋值给min
*/
void maxandmin(int *A, int n, int *max, int *min)
{
	if(n%2 == 1)//奇数
	{
		*min = A[0];
		*max = A[0];

		for(int i = 1; i < n; i+=2)
		{
			if(A[i] > A[i+1])
			{
				if(A[i]>max)
					max = A[i];
				if(A[i+1]<min)
					min = A[i+1];
			}
			else
			{
				if(A[i+1]>max)
					max = A[i+1];
				if(A[i]<min)
					min = A[i];
			}
		}//for
	}
	else
	{

	}

}


/*
	快速分类算法中，如何选取一个界值（又称为轴元素），影响着快速分类的效率，
	而且界值也并不一定是被分类序列中的一个元素。
	例如，我们可以用被分类序列中所有元素的平均值作为界值。编写算法实现以平均值为界值的快速分类方法。
*/
int average(int *A, int p, int r)
{
	int sum = 0;
	for(int i = p; i <= r; i++)
		sum += A[i];

	return sum/(r-p+1);
}

int partition_aver(int *A, int p, int r,int aver)
{
	int i = p, j = r;
	while(1)
	{
		while(A[i]<=aver && i<r)
			i++;
		while(A[j]>aver)
			j--;
		if(i>=j)
			break;
		swap(A,i,j);
	}

	return j;
}

void quicksort(int *A, int p, int r)
{
	if(p<r)
	{
		int aver = average(A, p, r);
		int q = partition_aver(A, p, r, aver);
		quicksort(A, p, q);
		quicksort(A, q+1, r);
	}
}

/*
	设数组A是n个数的序列，其中出现次数最多的数称为众数，他出现的次数叫做他的重数，
	设计算法求A的众数和重数（用递归和分治来做）
*/

/*
	 输入文件共2行，第一行表示该树的前序遍历结果，第二行表示该树的后序遍历结果
	 输出文件只包含一个不超过长整型的整数，表示可能的中序遍历序列的总数。
*/
//以分治法来做
int t = 0;
void inorderCount(int *pre, int *post, int l1, int h1, int l1, int h2)
{
	if(l1<h1 && l2<h2)
	{
		if(pre[l1+1] == post[h2-1])
			t = t*2;
		inorderCount(pre, post, l1+1, h1, l2, h2-1);
	}
	else
	{
		int i=l2;
		while(pre[l1+1] != post[i])
			i++;
		inorderCount(pre, post, l1+1, l1+1+i-l2, l2, i);
		inorderCount(pre, post, l1+1+i-l2+1, h1, i+1, h2);
	}
}

/*
	现在要把m本有顺序的书分给k给人复制（抄写），
	每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，
	分给每一个人的书，必须是连续的，
	比如不能把第一、第三、第四本书给同一个人抄写。
	现在请你设计一种方案，使得复制时间最短。
	复制时间为抄写页数最多的人用去的时间。

	输入格式：
	第一行两个整数m，k；（k≤m≤500）
	第二行m个整数，第i个整数表示第i本书的页数。
	输出格式：
	共k行，每行两个整数，第i行表示第i个人抄写的书的起始编号和终止编号。
	k行的起始编号应该从小到大排列，如果有多解，则尽可能让前面的人少抄写。
	输入样例#1：
	9 3
	1 2 3 4 5 6 7 8 9
	输出样例#1：
	1 5
	6 7
	8 9

	设f[i][j]为将第1本到第j本书交给i个人抄写的最短的时间
	设sum[k]为前k本书的总页数
	将书分为两个部分,前一个部分由i-1个人抄写,最后基本全给最后一个人抄写
	f[i][j] = min{ max{f[i-1][t], sum[j]-sum[t]} }
*/


/*
	设计单链表实现二进制加法
*/
void converse(char *c, int x)
{//十进制转换二进制
	Stack *S;
	int e, i=0;
	InitStack(S);

	while(x)
	{
		push(S, n%2);
		n = n/2;	
	}

	while(!stackempty(S))
	{
		pop(S,e);
		char c[i++] = e+48;
	}
}

void create(LinkList *L, char *c)
{
	int n = strlen(c);
	LinkList *p, pre = L;;

	for(int i = 0; i<n; i++)
	{
		p = (LinkList *)malloc(sizeof(LinkList));
		p -> data = c[i];
		pre -> next = p;
		pre = pre ->next;
		p -> next = NULL;
	}
}

void add(LinkList *L)
{//执行一次加1
	LinkList *p,*q;
	p = L->next;
	int i = 1;//进位标志

	while(p!=NULL)
	{
		if(p->data == 1 && i == 1)
		{
			p->data = 0;
			idx = 1;
		}
		else if(p->data == 0 &&i == 1)
		{
			p->data == 1;
			i = 0;
		}

		p = p->next;
	}

	p = L;

	if(i == 1)
	{//长度不够，增加结点
		q=(LinkList)malloc(sizeof(LNode));
        q->data=1;
        q->next=NULL;
        while(p->next!=NULL)
        {
            p=p->next;
        }
        p->next=q;

	}
}

//队列实现一个杨辉三角
void san(int n)
{
	int Q[1000];
	int f=0,r=0;
	Q[r++]=1;
	int i,j,x,y;
	for(i=2;i<=n;i++)
	{
		x=Q[f++];
		Q[r++]=1;
		for(j=i-2;j>0;j--)
		{
			y=Q[f++];
			Q[r++]=x+y;
			x=y;
		}
		Q[r++]=1;
	}
	for(i=1;i<=n;i++) 
	{
		for(j=i*(i-1)/2;j<i*(i-1)/2+i;j++)
		printf("%d ",Q[j]);
		printf("\n");
	}
}


int main(void)
{
	//combination(4,0,5);
	san(5);	
}